package second.codeTop.package2;

/**
 * @ClassName LC33
 * @description:
 * @author: 荣燊
 * @create: 2022-04-11 15:29
 **/
public class LC33 {
    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
    }

    // 搜索旋转排序数组
    public static int search(int[] nums, int target) {
        // 二分法，一定有一个数组是有序的，一个是无序的，循环分下去
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int mid = (left+right) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[0] <= nums[mid]) { //左边有序
                if (nums[0] <= target && target < nums[mid]) { //左侧有序
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { //右边有序
                if (nums[mid] < target && target <= nums[nums.length-1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
